package com.ruoyi.system.exper;


import com.sun.jmx.remote.internal.ArrayQueue;

import java.util.*;

public class Client {


    // 给定一个只包括 '(', ')', '{', '}', '\[', '\]' 的字符串 s ，判断字符串是否有
    //效。  ([)]   {{}}
    public static Boolean pattern1(String s) {
        if (s == null || s.length() == 0) {
            return true;
        }
        char[] chars = s.toCharArray();
        Stack<Character> strings = new Stack<>();
        char last = chars[0];
        for (char aChar : chars) {
            if (!strings.empty()) {
                last = strings.get(strings.size() - 1);
            }
            if ('(' == last) {
                if (')' == aChar) {
                    strings.pop();
                    continue;
                }
            } else if ('{' == last) {
                if ('}' == aChar) {
                    strings.pop();
                    continue;
                }
            } else if ('[' == last) {
                if (']' == aChar) {
                    strings.pop();
                    continue;
                }
            }
            strings.push(aChar);
            last = aChar;

        }
        return strings.empty();
    }

    // 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
    public static int minString(String s) {
        if (s == null && s.length() == 0) {
            return 0;
        }
        // 此字符串有效
        char[] chars = s.toCharArray();
        int length = chars.length;
        int maxlenth = 0;
        HashMap<Character, Integer> characterIntegerHashMap = new HashMap<>();
        int lastindex = 0;
        Boolean tag = true;
        for (int i = 0; i < length; i++) {
            // 如果包含则替换掉
            if (characterIntegerHashMap.containsKey(chars[i])) {
                lastindex = Math.max(characterIntegerHashMap.get(chars[i]), lastindex);
                maxlenth = Math.max(i - lastindex, maxlenth);
                tag = false;
            }
            characterIntegerHashMap.put(chars[i], i);
        }
        if (tag) {
            maxlenth = Math.max(characterIntegerHashMap.get(chars[length - 1]) - lastindex + 1, maxlenth);
        }

        return maxlenth;

    }


    //  运用滑动窗口
    public static int minString1(String s) {

        int length = s.length();
        int rk = -1;
        HashSet<Character> characters = new HashSet<>();
        int max = 0;
        for (int i = 0; i < length; i++) {

            if (!characters.isEmpty()) {

                characters.remove(s.charAt(i));
            }
            while (rk + 1 < length && !characters.contains(s.charAt(rk + 1))) { // 不包含
                rk++;
                characters.add(s.charAt(i));
                max = Math.max(rk - i + 1, max);
            }

        }


        return max;

    }


    //  运用滑动窗口
    public static int minString2(String s) {

        // 移动指针 ，左指针和右指针
        HashMap<Character, Integer> characterIntegerHashMap = new HashMap<>();
        int length = s.length();
        int left = -1;
        int max = 0;
        for (int i = 0; i < length; i++) {
            if (characterIntegerHashMap.containsKey(s.charAt(i))) {
                // 把左边的指针换成当前这个数
                left = characterIntegerHashMap.get(s.charAt(i));
            } else {

            }
            characterIntegerHashMap.put(s.charAt(i), i);
            max = Math.max(max, i - left);
        }


        return max;

    }

    /**
     * 最短路径和
     *
     * @param arr
     * @return
     */
    public static void minSum(int[][] arr) {

        ArrayList<Integer> integers = new ArrayList<>();
        recur(arr, 0, 0, 0, integers);
    }

    /**
     * 深度优先，递归循环
     *
     * @param arr
     * @param m   数组下标 "i"
     * @param n   数组下标 "j";
     * @param sum 当前路径和
     * @return
     */
    public static void recur(int[][] arr, int m, int n, int sum, ArrayList<Integer> integers) {


        // 递归和循环应该是等价的
        while (n < arr[0].length && m < arr.length) {
            sum += arr[m][n];
            while (m + 1 < arr.length) {

            }


        }

        if (n < arr[0].length && m < arr.length) {
            sum += arr[m][n];
            if (m == arr[0].length - 1 && n == arr.length - 1) {
                min = Math.min(sum, min);
                return;
            }
            // 往下走
            recur(arr, m + 1, n, sum, integers);
            // 往右走
            recur(arr, m, n + 1, sum, integers);
        }

        if (m < arr.length - 1 && n == arr[0].length) {
            while (m < arr.length - 1) {
                sum += arr[++m][n - 1];
            }
            min = Math.min(sum, min);
            return;
        }
        if (m == arr.length && n < arr[0].length - 1) {
            while (n < arr[0].length - 1) {
                sum += arr[m - 1][++n];
            }
            min = Math.min(sum, min);
            return;
        }
    }


    private static int min = 0;


    public static int lengthOfLongestSubstring(String s) {

        int length = s.length();
        HashSet<Character> characters = new HashSet<>();
        int rk = -1;
        int max = 0;
        for (int i = 0; i < length; i++) {
            // 移动左边的
            if (i != 0) {
                characters.remove(s.charAt(i - 1));
            }
            // 移动右边的
            while (rk + 1 < length && !characters.contains(s.charAt(rk + 1))) {
                characters.add(s.charAt(rk + 1));
                ++rk;
            }
            max = Math.max(max, rk - i + 1);
        }

        return max;
    }


    public static int lengthOfLongestSubstring1(String s) {
        // 滑动窗口，肯定有两个指针。。 第一个和第二个，，
        int length = s.length();
        int rk = -1;
        int max = 0;
        HashSet<Character> characters = new HashSet<>();
        for (int i = 0; i < length; i++) {
            if (i != 0) {
                characters.remove(s.charAt(i));
            }
            while (rk + 1 < length && !characters.contains(s.charAt(rk + 1))) {
                characters.add(s.charAt(i + 1));
                rk++;
            }
            max = Math.max(max, rk - i + 1);
        }
        return max;
    }


    public int minPathSum(int[][] grid) {
        // 动态规划 需要找到状态转移方程
        // 最大值
        int row = grid.length;
        int column = grid[0].length;
        int[][] ints = new int[row][column];
        ints[0][0] = grid[0][0];
        // 因为只能向下或者向右，所以第一列 和第一行的 比较固定
        for (int i = 1; i < row; i++) {
            ints[i][0] = ints[i - 1][0] + grid[i][0];
        }

        for (int j = 1; j < column; j++) {
            ints[0][j] = ints[0][j - 1] + grid[j][0];
        }
        // 正常的循环时，， 要么是从左边过来，要么是从上面下来

        for (int i = 1; i < row; i++) {

            for (int j = 1; j < column; j++) {
                ints[i][j] = Math.min(ints[i - 1][j], ints[i][j - 1]) + grid[i][j];
            }
        }
        return ints[row - 1][column - 1];
    }

    public int maxProfit(int[] prices) {
        int length = prices.length;
        int[][] dp = new int[length][2];
        // n  0代表持有，1代表 不持有
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        for (int i = 1; i < length; i++) {
            // 第 i 天持有
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            // 第 i 天不持有
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
        }
        return dp[prices.length - 1][1];

    }

    // 查找岛屿
    public int numIslands(char[][] grid) {

        int row = grid.length;
        int cloumn = grid[0].length;
        int existIsland = 0;

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < cloumn; j++) {
                if ('1' == grid[i][j]) {
                    // 至少存在一个岛屿
                    existIsland++;
                    dfs(grid, i, j);

                }


            }
        }


        return 0;
    }

    private void dfs(char[][] grid, int i, int j) {

        int row = grid.length;
        int cloumn = grid[0].length;

        if (i >= row || i < 0 || j >= cloumn || j < 0 || '0' == grid[i][j]) {
            return;
        }
        grid[i][j] = '0';
        // 遍历下一个
        // 前一个
        dfs(grid, i - 1, j);
        dfs(grid, i + 1, j);
        dfs(grid, i, j - 1);
        dfs(grid, i, j + 1);


    }


    public void solve(char[][] board) {
        // 先遍历
        int row = board.length;
        int cloumn = board[0].length;
        int[][] mark = new int[row][cloumn];
        int index = 1;
        HashMap<Integer, Boolean> integerBooleanHashMap = new HashMap<>();
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < cloumn; j++) {
                // 若果存在'O'  则遍历
                if ('X' == board[i][j]) {
                    //  是否存在被包围的闭环
                    Boolean aBoolean = dfsX(board, i, j, mark, index);
                    integerBooleanHashMap.put(index, aBoolean);
                    index++;
                    //  如果存在闭环，则进行更新
                }
            }
        }

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < cloumn; j++) {
                int mar = mark[i][j];
                if (mar != 0 && integerBooleanHashMap.get(mar)) {
                    board[i][j] = 'X';
                }
            }
        }


    }

    private Boolean dfsX(char[][] board, int i, int j, int[][] mark, int index) {
        int row = board.length;
        int cloumn = board[0].length;
        if (i == row || j == cloumn || i < 0 || j < 0) {
            return false;
        }
        if (board[i][j] == 'X') {
            return true;
        }
        // 标记已经访问过了
        mark[i][j] = index;
        return dfsX(board, i - 1, j, mark, index) &&
                dfsX(board, i + 1, j, mark, index) &&
                dfsX(board, i, j - 1, mark, index) &&
                dfsX(board, i, j + 1, mark, index);

    }


    //定义匹配的四个坐标

    int[] dx = {1, -1, 0, 0};
    int[] dy = {0, 0, -1, 1};

    public void solveg(char[][] board) {

        Queue<int[]> queue = new LinkedList<int[]>();

        int row = board.length;
        int column = board[0].length;
        // 其实就只用循环四周就OK了
        for (int i = 0; i < row; i++) {
            if (board[i][0] == 'O') {
                queue.add(new int[]{i, 0});
                board[i][0] = 'A';
            }
            if (board[i][column - 1] == 'O') {
                queue.add(new int[]{i, 0});
                board[i][0] = 'A';
            }
        }
        for (int j = 1; j < column - 1; j++) {
            if (board[0][j] == 'O') {
                queue.add(new int[]{j, 0});
                board[j][0] = 'A';
            }
            if (board[row - 1][j] == 'O') {
                queue.add(new int[]{j, 0});
                board[j][0] = 'A';
            }
        }
        // 存好了边界条件
        while (!queue.isEmpty()) {
            // 弹出第一个，
            int[] poll = queue.poll();
            int x = poll[0];
            int y = poll[1];
            for (int i = 0; i < 4; i++) {
                int mx = x + dx[i];
                int my = y + dy[i];
                if (board[mx][my] == 'O') {
                    // 如果是相邻的 'O'
                    queue.add(new int[]{x + dx[i], y + dy[i]});
                    board[mx][my] = 'A';
                }
            }
        }
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < column; j++) {
                if (board[i][j] == 'A') {
                    board[i][j] = 'O';
                } else if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
            }

        }

    }




     // 选满
    public static int knapsack(int[] weight, int[] value, int maxweight) {

        // 动态规划  重量和 物品
        int n = value.length;
        int[][] dp = new int[n][maxweight + 1];
        try {
            for (int i = 0; i < n; i++) {
                for (int j = 1; j < maxweight + 1; j++) {
                    if (i == 0) { // 只选第一个的时候， 只有是整数倍才能有值，其他的都是最小值，，不能选的。
                        if (j >= weight[0] && j % weight[i] == 0) {
                            int k = j / weight[i];
                            // 第一个物品可以多次选择，只要满足条件
                            dp[i][j] = k * value[i];
                        } else {
                            dp[i][j] = Integer.MIN_VALUE;
                        }
                        continue;
                    }
                    if (j >= weight[i]) {
                        int k = j / weight[i];
                        for (int key = 0; key <= k; key++) {
                            dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - key * weight[i]] + key * value[i]);
                        }
                    } else {
                        dp[i][j] = dp[i - 1][j];
                    }

                }
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
        return dp[n - 1][maxweight];
    }

    public static void main(String[] args) {

        // 


    }


}
